#include <stdio.h>
void linearHashTable(int arr[], int num, int p ){
	printf("线性探测\n");
	int hashTable[13] = {0};
	for (int i = 0; i < num; ++i)
	{
		int index = arr[i] % p ; 
		while(hashTable[index]!=0){
			index++;
			if(index==13){
				index = 0;
			}
		}
		hashTable[index] = arr[i];
	}
	for (int i = 0; i < 13; ++i)
	{
		printf("%d ",hashTable[i] );
	}
	printf("\n");
}
void squareHashTable(int arr[],int num, int p ){
	printf("平方探测\n");
	int hashTable[13] = {0};
	for (int i = 0; i < num; ++i)
	{
		int index = arr[i] % p ;
		int flag = 1; 
		int s = 0;
		while(hashTable[index]!=0){
			index = arr[i] % p ;
			s++;
			int ss;
			if(s%2==0){
				ss = s / 2;
			}else{
				ss = s / 2 + 1;
			}
			index += (ss*ss*flag);
			if(flag==1){
				flag = -1;
			}else{
				flag = 1;
			}
			while(index>=13){
				index -= 13;
			}
			while(index<0){
				index += 13;
			}
		}
		hashTable[index]=arr[i];
	}
	for (int i = 0; i < 13; ++i)
	{
		printf("%d ",hashTable[i]);
	}
	printf("\n");
}
int main(int argc, char const *argv[])
{
	int arr[10] = {23,34,12,56,76,87,48,99,58,47};
	int p = 11;
	//4k - 3 质数
	linearHashTable(arr,10,p);
	squareHashTable(arr,10,p);
	return 0;
}